#第七章 练习题第一题A项的图(116页) 通过狄克斯特拉算法计算最短路径
# dijkstra's
start = 'start'
fin = 'fin'

graph = {}

#起点邻居
graph[start] = {}
graph[start]['a'] = 2
graph[start]['c'] = 5

#a点邻居
graph['a'] = {}
graph['a']['b'] = 7
graph['a']['c'] = 8

#b点邻居
graph['b'] = {}
graph['b'][fin] = 1

#c点邻居
graph['c'] = {}
graph['c']['b'] = 2
graph['c']['d'] = 4

#d点邻居
graph['d'] = {}
graph['d']['b'] = 6
graph['d'][fin] = 3

graph[fin] = {}


#待检测列表,各个点的消耗
costs = {}
costs['a'] = 2
costs['c'] = 5
costs[fin] = float('inf')

processeds = []
parents = {'a':start,'c':start}

def lowest_node(costs):
    minVal = float('inf')
    lowest_node = None
    for k,v in costs.items():
        if v <= minVal and k not in processeds:
            minVal = v
            lowest_node = k
    print("lowest_node",lowest_node)
    return lowest_node

node = lowest_node(costs)

while node is not None:
    cost = costs[node]
    neighbors = graph[node]
    print('node,neighbors=',node,neighbors)    
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        if n not in costs:#表示不能从起点直接到达该点
            costs[n] = cost + neighbors[n]
            parents[n] = node

        if n in costs and costs[n] > new_cost:
            costs[n] = new_cost
            parents[n] = node    
    processeds.append(node)
    node = lowest_node(costs)

print('parents',parents)
print("costs",costs)

#推算出路径
def find_path():
    paths = []
    paths.append(fin)
    curNode = parents[fin]
    paths.append(curNode)
    while curNode and curNode != start:        
        curNode = parents[curNode]
        paths.append(curNode)    
    paths.reverse()
    return paths

p = find_path()

print("p=",p)



